Non-graphical overlapping rectangles test

Ron Savage on 2008-06-09T03:25:01

I'm looking at the problem of drawing labels on a graph, e.g street names, which might overlap.

What I want, so I don't have to write it myself, is a module which takes 2 rectangles defined by their corners, and gives me a Boolean result as to whether or not the 2 rectangles overlap.

I don't want to be tied to any particular image processing software, e.g. Image::Magick, and I don't need the result to be the polygon defined by the overlap.

I can see an algorithm: Take the 2 end lines [*] of one rectangle, determine their equations, and see if they intersect any of the sides of the other rectangle. Then reverse the roles of the 2 rectangles to check the opposite case.

[*] For 2 lines meeting at the corner, it doesn't matter which of the 2 lines is used. So 2 bounding lines of a rectangle which don't meet ought to be sufficient.

Has this been done?

Are there any modules which do part of it?

I searched CPAN for Math::*, but did not see anything obviously relevant.

---

Pretty straightforward calculation

grink on 2008-06-09T05:14:35

If I understand your problem description correctly:

This is a pretty common problem typical of interactive 2d applications (a.k.a video games).

A good algorithm is really straightforward.

Search for AABB (Axis-aligned bounding box) and OBB (Oriented bounding box) collision tests.

Depending on the number of tests you need to do, speed may or may not be an issue. You can speed-up the solve time by testing in the following order:

1. Do two BSs (bounding sphere) overlap?
2. Now, do the AABBs overlap?
3. Finally, do the OBBs overlap?

Re:Pretty straightforward calculation

Ron Savage on 2008-06-09T23:21:56

$many x $thanx;

Your comments gave me much to search for and read about.

Looks like the AABB is painless and the OBB is painful.

Answer the negative

rhesa on 2008-06-09T10:24:45

The rectangles _don't_ overlap when one is either completely to the left of the other, or completely below the other.

A rectangle can be defined by the coordinates of its top-left and bottom-right points:

So let's say A = (x1,y1,x2,y2) and B = (u1,v1,u2,v2).

(x1,y1)                 (u1,v1)
  +-------------+           +-----------+
  |             |           |           |
  |     A       |           |     B     |
  |             |           |           |
  +-------------+           +-----------+
              (x2,y2)                 (u2,v2)

Then A does not overlap B if one of these four tests pass:

# A left of B
x2 < u1
# A right of B
x1 > u2
# A above B
y2 > v1
# A below B
y1 < v2

So A overlaps B if none of the above hold:

  not ( x2 < u1 or x1 > u2 or y2 > v1 or y1 < v2 )

or equivalently ( !(a or b) <=> !a and !b )

  x2 >= u1 and x1 <= u2 and y2 <= v1 and y1 >= v2

That's too simple to be a module :-)